package com.wfm.common;

import java.util.Arrays;
import org.junit.Test;

/**
 * 并查集，一种树形结构，用于处理一些不想交集合的合并和查询问题，尝尝在使用中以森林来表示
 */
public class DisjointSets {
    public int[] parent; // 保存节点i的父节点
    public int[] size;  // 保存节点i为根的树的个数
    public int n;   // 节点个数
    public int setCount; // 当前连通分量数目

    public DisjointSets(int n) {
        this.n = n;
        this.setCount = n;
        this.parent = new int[n];
        this.size = new int[n];
        Arrays.fill(size, 1);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        // 判断自己的父亲是不是自己，也就是判断是不是单个节点
        // 不是则递归，让自己的直接父节点改成指向根节点
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    }

    // 要让小的size加入大的size
    // 我们假设都是y小x大，也就是y的父节点是x，如果y>x就交换
    public void merge(int x, int y) {
        x = find(x);
        y = find(y);

        // 同一个节点，没必要合并
        if (x == y) {
            return;
        }

        if (size[x] < size[y]) {
            int temp = x;
            x = y;
            y = temp;
        }
        parent[y] = x;
        size[x] += size[y];
        --setCount;
    }

    public boolean connected(int x, int y) {
        x = find(x);
        y = find(y);
        return x == y;
    }

    public static void main(String[] args) {
        DisjointSets disjointSets = new DisjointSets(10);
        disjointSets.merge(0,1);
        disjointSets.merge(2,0);
        disjointSets.merge(9,2);
        System.out.println(disjointSets.find(9));
        System.out.println(disjointSets.find(0));
        System.out.println(disjointSets.find(2));
        System.out.println(disjointSets.find(1));
        System.out.println(disjointSets.find(3));
        System.out.println(disjointSets.find(4));
        System.out.println(disjointSets.find(5));
    }
}
